Java8 CopyOnWriteArrayList 源码解析

前言

一看这个，咋这么长的名字，记起来有点麻烦呀！这个类使用的情况不多，最近在看EventBus的时候看到过，所以还是跳出来学习一下，看一下这个类的庐山真面目

是什么东西？

CopyOnWrite，大概能猜到跟写时复制有关，为什么要有这个东西？不难想出这是为了线程安全而设计的，否则直接用 ArrayList 就行了，那好了，说的这个东西就是一个ArrayList ，在此基础上，他是线程安全的，采用了写时复制的方法，那我们可以思考一下，他是怎么做的，如果给我们设计，我们要怎么做呢？

前世今生

它没有扩展 ArrayList，即使是以此结尾，直接实现了 List，也实现了RandomAccess，Cloneable， Serializable 接口，Doug Lea 写的，就是厉害

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

源码解析

属性

• 我们看到了一个锁，聪明的你可能想到了，是不是可以加锁来实现线程的安全？在写的时候加锁，读的时候可以不用锁
• 同样使用了 Volatile 的 Object 数组存储元素
• 两个final 方法设置 elements

/**
 * The lock protecting all mutators.  (We have a mild preference
 * for builtin monitors over ReentrantLock when either will do.)
 */
final transient Object lock = new Object();

/** The array, accessed only via getArray/setArray. */
// Android-changed: renamed array -> elements for backwards compatibility b/33916927
private transient volatile Object[] elements;

/**
 * Gets the array.  Non-private so as to also be accessible
 * from CopyOnWriteArraySet class.
 */
final Object[] getArray() {
    return elements;
}

/**
 * Sets the array.
 */
final void setArray(Object[] a) {
    elements = a;
}

构造函数，默认大小为0，也可以传入集合类对象进行复制，或者直接传入数组，这里用到了 Arrays.copyOf，这是一个数组复制的静态函数，底层使用了System.arraycopy，效率很高，反悔了一个新的数组

/**
 * Creates an empty list.
 */
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

/**
 * Creates a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection of initially held elements
 * @throws NullPointerException if the specified collection is null
 */
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        elements = c.toArray();
        // defend against c.toArray (incorrectly) not returning Object[]
        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}

/**
 * Creates a list holding a copy of the given array.
 *
 * @param toCopyIn the array (a copy of this array is used as the
 *        internal array)
 * @throws NullPointerException if the specified array is null
 */
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

函数

get 没有加锁，直接返回，由于volatile，能保证读到最新的值

private E get(Object[] a, int index) {
    return (E) a[index];
}

set，果不其然，对添加数据使用了加锁，首先检查这个位置是否存在对象，如果不存在，那么需要拷贝一个新的数组，并且添加一个元素，在调用elements更新属性；如果存在了，也需要设置数组，保证volatile的语义，这里不是很明白，既然都加了锁，不需要更新数据时还要更新数据。最后返回 oldValue。
至于为什么，在这里看到有人讨论 concurrency-interest，但感觉也没有数清楚，不过我看到了，之前的jdk版本使用了 Lock而不是 synchronized ，可见synchronized 的性能以及大大提高

public E set(int index, E element) {
    synchronized (lock) {
        Object[] elements = getArray();
        E oldValue = get(elements, index);

        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    }
}

add，依然使用锁，同样先读数组，在复制出一个新的数组，注意，数组长度为 len + 1，预留了一个位置，因此这个数据结构并没有类似 *2 的扩容机制，而是一个一个添加，个人觉得这样效率会大打折扣，当然，为了 tradeoff。在添加元素，最后返回true

public boolean add(E e) {
    synchronized (lock) {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    }
}

add，在某个位置插入一个元素，首先先检查index，看是否越界，这里使用了一个小技巧，计算了移动距离，如果为0，即添加到最后，则直接复制，否则就需要调用两次 copy 函数进行复制

public void add(int index, E element) {
    synchronized (lock) {
        Object[] elements = getArray();
        int len = elements.length;
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException(outOfBounds(index, len));
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            newElements = new Object[len + 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        newElements[index] = element;
        setArray(newElements);
    }
}

remove 可以删除某个索引的元素

public E remove(int index) {
    synchronized (lock) {
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    }
}

remove也可以删除某个对象，不过需要遍历数组

public boolean remove(Object o) {
    Object[] snapshot = getArray();
    int index = indexOf(o, snapshot, 0, snapshot.length);
    return (index < 0) ? false : remove(o, snapshot, index);
}

private static int indexOf(Object o, Object[] elements,
                           int index, int fence) {
    if (o == null) {
        for (int i = index; i < fence; i++)
            if (elements[i] == null)
                return i;
    } else {
        for (int i = index; i < fence; i++)
            if (o.equals(elements[i]))
                return i;
    }
    return -1;
}

最后还是调用这个，也是线程安全的函数，逻辑也很简单

private boolean remove(Object o, Object[] snapshot, int index) {
    synchronized (lock) {
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) findIndex: {
            int prefix = Math.min(index, len);
            for (int i = 0; i < prefix; i++) {
                if (current[i] != snapshot[i]
                    && Objects.equals(o, current[i])) {
                    index = i;
                    break findIndex;
                }
            }
            if (index >= len)
                return false;
            if (current[index] == o)
                break findIndex;
            index = indexOf(o, current, index, len);
            if (index < 0)
                return false;
        }
        Object[] newElements = new Object[len - 1];
        System.arraycopy(current, 0, newElements, 0, index);
        System.arraycopy(current, index + 1,
                         newElements, index,
                         len - index - 1);
        setArray(newElements);
        return true;
    }
}

removeRange 删除一定范围，不用说了，相信他的代码你早就知道该怎么写了

void removeRange(int fromIndex, int toIndex) {
    synchronized (lock) {
       .....
    }
}

addIfAbsent 如果不存在才添加

public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}

/**
 * A version of addIfAbsent using the strong hint that given
 * recent snapshot does not contain e.
 */
private boolean addIfAbsent(E e, Object[] snapshot) {
    synchronized (lock) {
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) {
            // Optimize for lost race to another addXXX operation
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if (current[i] != snapshot[i]
                    && Objects.equals(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0)
                    return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    }
}

类似还有 addAllIfAbsent，写得还是很不错的，毕竟是 Doug Lea

public int addAllAbsent(Collection<? extends E> c) {
    Object[] cs = c.toArray();
    if (cs.length == 0)
        return 0;
    synchronized (lock) {
        Object[] elements = getArray();
        int len = elements.length;
        int added = 0;
        // uniquify and compact elements in cs
        for (int i = 0; i < cs.length; ++i) {
            Object e = cs[i];
            if (indexOf(e, elements, 0, len) < 0 &&
                indexOf(e, cs, 0, added) < 0)
                cs[added++] = e;
        }
        if (added > 0) {
            Object[] newElements = Arrays.copyOf(elements, len + added);
            System.arraycopy(cs, 0, newElements, len, added);
            setArray(newElements);
        }
        return added;
    }
}

小结

分析别人的源码的过程本身就是一个学习的过程，能从中学到很多新的东西，并且能够巩固以前的知识。

欢迎讨论～